#include "AVL.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void update_height(Node *root)
{
  int maxh;
  // no child
  if (root->left == NULL && root->right == NULL)
  {
    maxh = -1;
    root->height = maxh + 1;
    return;
  }
  // only left child
  if (root->right == NULL)
  {
    maxh = root->left->height;
    root->height = maxh + 1;
    return;
  }
  // only right child
  if (root->left == NULL)
  {
    maxh = root->right->height;
    root->height = maxh + 1;
    return;
  }
  // two child
  if (root->left->height >= root->right->height)
    maxh = root->left->height;
  else
    maxh = root->right->height;
  root->height = maxh + 1;
  return;
}

void rightRotate(Node **proot)
{
  Node *k2 = *proot;
  Node *k1 = k2->left;
  Node *Y = k1->right;
  *proot = k1;
  k1->right = k2;
  k2->left = Y;
  update_height(k2);
  update_height(k1);
  return;
}

void leftRotate(Node **proot)
{
  Node *k2 = *proot;
  Node *k1 = k2->right;
  Node *Y = k1->left;
  *proot = k1;
  k1->left = k2;
  k2->right = Y;
  update_height(k2);
  update_height(k1);
  return;
}

void rebalance(Node **proot)
{
  Node *root = *proot;

  int flag_l = 0;
  int flag_r = 0;
  int left_height, right_height;
  if (root->left == NULL)
  {
    left_height = -1;
    flag_l = 1;
  }
  else
    left_height = root->left->height;
  if (root->right == NULL)
  {
    right_height = -1;
    flag_r = 1;
  }
  else
    right_height = root->right->height;
  // if balanced
  if (abs(left_height - right_height) <= 1)
    return;
  if (flag_l == 0) // avoid null pointer
  {
    // left left case
    if (root->left->left != NULL)
    {
      rightRotate(proot);
      return;
    }
    // left right case
    if (root->left->right != NULL)
    {
      leftRotate(&(root->left));
      rightRotate(proot);
      return;
    }
  }
  if (flag_r == 0) // avoid null pointer
  {
    // right right case
    if (root->right->right != NULL)
    {
      leftRotate(proot);
      return;
    }
    // right left case
    if (root->right->left != NULL)
    {
      rightRotate(&(root->right));
      leftRotate(proot);
      return;
    }
  }
}

Node *insertNode(Node **proot, int x)
{
  Node *root = *proot;

  if (root == NULL)
  {
    // create new node
    Node *newRoot = (Node *)malloc(sizeof(Node));
    newRoot->key = x;
    newRoot->height = 0;
    newRoot->left = NULL;
    newRoot->right = NULL;
    return *proot = newRoot;
  }

  // duplicated key, do nothing
  if (root->key == x)
    return NULL;

  Node *newNode;
  if (root->key > x)
    newNode = insertNode(&(root->left), x); // x is smaller than root, insert left
  else
    newNode = insertNode(&(root->right), x); // x is bigger than root, insert right

  update_height(root);
  rebalance(proot);
  return newNode;
}

Node *deleteMin(Node **proot)
{
  Node *root = *proot;
  Node *minNode;

  // no left child, it's the min node
  if (root->left == NULL)
  {
    minNode = root;
    *proot = root->right;
    return minNode;
  }
  minNode = deleteMin(&(root->left));
  update_height(root);
  rebalance(proot);
  return minNode;
}

Node *deleteRoot(Node **proot)
{
  Node *root = *proot;
  // remove and return root
  Node *currNode = *proot;
  if (root->left == NULL)
  {
    *proot = root->right;
    return currNode;
  }
  if (root->right == NULL)
  {
    *proot = root->left;
    return currNode;
  }
  // root has two children
  Node *minNode = deleteMin(&(root->right));
  minNode->left = root->left;
  minNode->right = root->right;
  *proot = minNode;
  return currNode;
}

Node *deleteNode(Node **proot, int x)
{
  Node *root = *proot;
  Node *matchNode;
  // no such node
  if (root == NULL)
    return NULL;
  if (root->key > x)
    matchNode = deleteNode(&(root->left), x);
  else if (root->key < x)
    matchNode = deleteNode(&(root->right), x);
  else
    matchNode = deleteRoot(proot);
  update_height(root);
  rebalance(proot);
  return matchNode;
}

Node *findNode(Node *root, int x)
{
  // no such node
  if (root == NULL)
    return NULL;

  // base case, node found
  if (root->key == x)
    return root;

  // search subtree
  if (root->key > x)
    return findNode(root->left, x);
  return findNode(root->right, x);
}

void destroyTree(Node **proot)
{
  Node *root = *proot;

  // no such node
  if (root == NULL)
    return;

  // if node has child
  if (root->left != NULL || root->right != NULL)
  {
    destroyTree(&(root->left));
    destroyTree(&(root->right));
  }

  // if node is a leaf
  free(root);
  *proot = NULL;
  return;
}

typedef struct asciinode_struct asciinode;

struct asciinode_struct
{
  asciinode *left, *right;

  // length of the edge from this node to its children
  int edge_length;

  int height;

  int lablen;

  //-1=I am left, 0=I am root, 1=right
  int parent_dir;

  // max supported unit32 in dec, 10 digits max
  char label[11];
};

#define MAX_HEIGHT 1000
int lprofile[MAX_HEIGHT];
int rprofile[MAX_HEIGHT];
#define INFINITY (1 << 20)

// adjust gap between left and right nodes
int gap = 3;

// used for printing next node in the same level,
// this is the x coordinate of the next char printed
int print_next;

int MIN(int X, int Y)
{
  return ((X) < (Y)) ? (X) : (Y);
}

int MAX(int X, int Y)
{
  return ((X) > (Y)) ? (X) : (Y);
}

asciinode *build_ascii_tree_recursive(Node *t)
{
  asciinode *node;

  if (t == NULL)
    return NULL;

  node = (asciinode *)malloc(sizeof(asciinode));
  node->left = build_ascii_tree_recursive(t->left);
  node->right = build_ascii_tree_recursive(t->right);

  if (node->left != NULL)
  {
    node->left->parent_dir = -1;
  }

  if (node->right != NULL)
  {
    node->right->parent_dir = 1;
  }

  sprintf(node->label, "%d|%d", t->key, t->height);

  node->lablen = strlen(node->label);

  return node;
}

// Copy the tree into the ascii node structre
asciinode *build_ascii_tree(Node *t)
{
  asciinode *node;
  if (t == NULL)
    return NULL;
  node = build_ascii_tree_recursive(t);
  node->parent_dir = 0;
  return node;
}

// Free all the nodes of the given tree
void free_ascii_tree(asciinode *node)
{
  if (node == NULL)
    return;
  free_ascii_tree(node->left);
  free_ascii_tree(node->right);
  free(node);
}

// The following function fills in the lprofile array for the given tree.
// It assumes that the center of the label of the root of this tree
// is located at a position (x,y).  It assumes that the edge_length
// fields have been computed for this tree.
void compute_lprofile(asciinode *node, int x, int y)
{
  int i, isleft;
  if (node == NULL)
    return;
  isleft = (node->parent_dir == -1);
  lprofile[y] = MIN(lprofile[y], x - ((node->lablen - isleft) / 2));
  if (node->left != NULL)
  {
    for (i = 1; i <= node->edge_length && y + i < MAX_HEIGHT; i++)
    {
      lprofile[y + i] = MIN(lprofile[y + i], x - i);
    }
  }
  compute_lprofile(node->left, x - node->edge_length - 1, y + node->edge_length + 1);
  compute_lprofile(node->right, x + node->edge_length + 1, y + node->edge_length + 1);
}

void compute_rprofile(asciinode *node, int x, int y)
{
  int i, notleft;
  if (node == NULL)
    return;
  notleft = (node->parent_dir != -1);
  rprofile[y] = MAX(rprofile[y], x + ((node->lablen - notleft) / 2));
  if (node->right != NULL)
  {
    for (i = 1; i <= node->edge_length && y + i < MAX_HEIGHT; i++)
    {
      rprofile[y + i] = MAX(rprofile[y + i], x + i);
    }
  }
  compute_rprofile(node->left, x - node->edge_length - 1, y + node->edge_length + 1);
  compute_rprofile(node->right, x + node->edge_length + 1, y + node->edge_length + 1);
}

// This function fills in the edge_length and
// height fields of the specified tree
void compute_edge_lengths(asciinode *node)
{
  int h, hmin, i, delta;
  if (node == NULL)
    return;
  compute_edge_lengths(node->left);
  compute_edge_lengths(node->right);

  /* first fill in the edge_length of node */
  if (node->right == NULL && node->left == NULL)
  {
    node->edge_length = 0;
  }
  else
  {
    if (node->left != NULL)
    {
      for (i = 0; i < node->left->height && i < MAX_HEIGHT; i++)
      {
        rprofile[i] = -INFINITY;
      }
      compute_rprofile(node->left, 0, 0);
      hmin = node->left->height;
    }
    else
    {
      hmin = 0;
    }
    if (node->right != NULL)
    {
      for (i = 0; i < node->right->height && i < MAX_HEIGHT; i++)
      {
        lprofile[i] = INFINITY;
      }
      compute_lprofile(node->right, 0, 0);
      hmin = MIN(node->right->height, hmin);
    }
    else
    {
      hmin = 0;
    }
    delta = 4;
    for (i = 0; i < hmin; i++)
    {
      delta = MAX(delta, gap + 1 + rprofile[i] - lprofile[i]);
    }

    // If the node has two children of height 1, then we allow the
    // two leaves to be within 1, instead of 2
    if (((node->left != NULL && node->left->height == 1) ||
         (node->right != NULL && node->right->height == 1)) &&
        delta > 4)
    {
      delta--;
    }

    node->edge_length = ((delta + 1) / 2) - 1;
  }

  // now fill in the height of node
  h = 1;
  if (node->left != NULL)
  {
    h = MAX(node->left->height + node->edge_length + 1, h);
  }
  if (node->right != NULL)
  {
    h = MAX(node->right->height + node->edge_length + 1, h);
  }
  node->height = h;
}

// This function prints the given level of the given tree, assuming
// that the node has the given x cordinate.
void print_level(asciinode *node, int x, int level)
{
  int i, isleft;
  if (node == NULL)
    return;
  isleft = (node->parent_dir == -1);
  if (level == 0)
  {
    for (i = 0; i < (x - print_next - ((node->lablen - isleft) / 2)); i++)
    {
      printf(" ");
    }
    print_next += i;
    printf("%s", node->label);
    print_next += node->lablen;
  }
  else if (node->edge_length >= level)
  {
    if (node->left != NULL)
    {
      for (i = 0; i < (x - print_next - (level)); i++)
      {
        printf(" ");
      }
      print_next += i;
      printf("/");
      print_next++;
    }
    if (node->right != NULL)
    {
      for (i = 0; i < (x - print_next + (level)); i++)
      {
        printf(" ");
      }
      print_next += i;
      printf("\\");
      print_next++;
    }
  }
  else
  {
    print_level(node->left,
                x - node->edge_length - 1,
                level - node->edge_length - 1);
    print_level(node->right,
                x + node->edge_length + 1,
                level - node->edge_length - 1);
  }
}

// prints ascii tree for given Node structure
void printTree(Node *root)
{
  asciinode *proot;
  int xmin, i;
  if (root == NULL)
    return;
  proot = build_ascii_tree(root);
  compute_edge_lengths(proot);
  for (i = 0; i < proot->height && i < MAX_HEIGHT; i++)
  {
    lprofile[i] = INFINITY;
  }
  compute_lprofile(proot, 0, 0);
  xmin = 0;
  for (i = 0; i < proot->height && i < MAX_HEIGHT; i++)
  {
    xmin = MIN(xmin, lprofile[i]);
  }
  for (i = 0; i < proot->height; i++)
  {
    print_next = 0;
    print_level(proot, -xmin, i);
    printf("\n");
  }
  if (proot->height >= MAX_HEIGHT)
  {
    printf("(This tree is taller than %d, and may be drawn incorrectly.)\n", MAX_HEIGHT);
  }
  free_ascii_tree(proot);
}